package 动态规划.背包问题;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 背包01.java
 * @Description TODO
 * @createTime 2020年11月14日 08:15:00
 * 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
 *
 * 第 i 件物品的体积是 vi，价值是 wi。
 *
 * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 * 输出最大价值。
 *
 * 思路：很难凑出一个等式  因为体积和价值相互制约
 * 所以动态规划是要解决的主要时 如何平衡价值为体积 来保证总价值最大
 *                      也就是体积有边界的情况下 如何使得价值最大
 *                       也就是 两个变量 一个变量有边界 一个变量没有边界 其中一个变量会随着另一个变量的改变而改变
 *                                      求没有边界的变量的最大值
    1.用二维数组
        f[i][j]表示i个物品中 容积为j的情况下所能获得的最大价值
        f[i][j]=max(第i的选择，第i个不选择)
        第i个不选择：f[i][j]=f[i-1][j]
        第i个选择:f[i][j]=f[i-1][j-v[i]]+w[i]
    二维数组的行是体积 从0到v 记录下所有中情况 列是每一个物品 每一个物品都可以选和不选
            我们最后需要的是 最后一行的数据 表示i个物品从0到v分别可以获取的价值 找出最大的
            有点像控制变量法
 */

public class 背包01 {
    class Solution1{
//        int[] v={};//表示每个物品的体积
//        int[] w={};//表示每个物品的价值
//        int n=4,m=20;//表示在4个物品中 体积为20的前提下的最大价值
        public int erwei(int[] v,int[] w,int n,int m){
            int[][] f=new int[n+1][m+1];//f[0][0] 要初始化为00
            for(int i=1;i<=n;i++){
                for(int j=0;j<=m;j++){//对每个物品 体积从0到v都要探测一遍
                f[i][j]=f[i-1][j];//先假设不选择当前物品
                    if(j>=v[i]){//如果当前容积大于该物品的体积 就要进行选择
                        f[i][j]=Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
                    }
                }
            }


            int res=0;
            for(int i=0;i<=m;i++){
                res=Math.max(res,f[n][i]);//选择最后一行的最大值
            }

            return  res;//或者直接returndp[n][m]
        }

        public int yiwei(int[] v,int[] w,int n,int m){
            //用一维数组 体积倒过来表示 状态压缩，从后向前
            //从后往前 不断覆盖 二维数组是每一个物品的都写下来  一维数组是直接覆盖
            //                      一维数组只保留每个体积的最大值 二维数组则保留每个物品 每个体积的最大值
            int[] f=new int[m+1];
            for(int i=1;i<=n;i++){
                for(int j=m;j>=v[i];j--){
                    f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
                }
            }

            return f[m];
        }
    }
}